package main

import "fmt"

/**
C++内部sort实现，使用Go语言实现，来提高对Go语言熟练度
*/
const threshold = 16

type array struct {
	nums []int
}
type heaper interface {
	buildHeap(first int, last int)
	heapify(parent int, n int)
	heapSort(first int, last int)
}

type inserter interface {
	linearInsertion(first, last, value int)
	unguardedInsertion(last, value int)
}
type insertionSorter interface {
	linearInsertionSort(first int, last int)
	unguardedInsertionSort(first int, last int)
}

func copyBackward(begin, end, destination int, nums []int) {
	distance := end - begin
	for i := 0; i < distance; i++ {
		nums[destination-i] = nums[end-1-i]
	}
}
func (e array) linearInsertion(first, last, value int) {
	if value < e.nums[first] {
		copyBackward(first, last, last, e.nums)
		e.nums[first] = value
	} else {
		e.unguardedInsertion(last, value)
	}
}

func (e array) unguardedInsertion(last, value int) {
	var next int = last
	next--
	for value < e.nums[next] {
		e.nums[last] = e.nums[next]
		last = next
		next--
	}
	e.nums[last] = value
}

func (e array) linearInsertionSort(int, int) {
	for i := 1; i < len(e.nums); i++ {
		e.linearInsertion(0, i, e.nums[i])
	}
}

func (e array) unguardedInsertionSort(first, last int) {
	for i := first; i < last; i++ {
		e.unguardedInsertion(i, e.nums[i])
	}
}
func getMedian(nums []int) int {
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}

	length := len(nums)
	var a, b, c = nums[0], nums[length/2], nums[length-1]

	var biggestNum = max(a, max(b, c))
	if biggestNum == a {
		return max(b, c)
	}
	if biggestNum == b {
		return max(a, c)
	}
	if biggestNum == c {
		return max(a, b)
	}
	return 0
}

func getDepthLimits(size int) int {
	var ans int = 0
	for size >= 1 {
		size >>= 1
		ans++
	}
	return ans
}
func (e array) buildHeap(first, last int) {
	for i := (last - 1) / 2; i >= 0; i-- {
		e.heapify(i, last)
	}
}
func (e array) heapSort(first, last int) {
	e.buildHeap(first, last)

	for i := last; i >= 1; i-- {
		e.nums[0], e.nums[i] = e.nums[i], e.nums[0]
		e.heapify(0, i)
	}
}
func (e array) heapify(parent, n int) {
	var left, right, max = 2*parent + 1, 2*parent + 2, parent

	if left < n && e.nums[max] < e.nums[left] {
		max = left
	}
	if right < n && e.nums[max] < e.nums[right] {
		max = right
	}

	if e.nums[max] != e.nums[parent] {
		e.nums[max], e.nums[parent] = e.nums[parent], e.nums[max]
		e.heapify(max, len(e.nums))
	}
}

func introSort(e array, first, last, depthLimits int) {
	//TODO 内省排序
	for last-first > threshold {
		if depthLimits == 0 {
			e.heapSort(first, last)
			return
		}
		depthLimits--
		cut := unguardedPartition(e, first, last, getMedian(e.nums))

		introSort(e, cut, last, depthLimits) // 递归解决右半区间
		last = cut                           // 循环处理左半区间
	}
}
func unguardedPartition(e array, first, last, pivot int) int {
	for {
		for e.nums[first] < pivot {
			first++
		}

		last--
		for e.nums[last] > pivot {
			last--
		}

		if first >= last {
			return first
		}
		e.nums[first], e.nums[last] = e.nums[last], e.nums[first]
		first++
	}
}
func finalSort(e array) {
	//TODO 处理小区块
	if len(e.nums) > 16 {
		e.linearInsertionSort(0, threshold)
		e.unguardedInsertionSort(threshold, len(e.nums))
	} else {
		e.linearInsertionSort(0, len(e.nums))
	}
}
func Sort(e array) {
	//TODO: 排序入口函数
	depthLimits := getDepthLimits(len(e.nums))
	introSort(e, 0, len(e.nums), depthLimits)
	finalSort(e)
}

func main() {
	var jj array
	var test = [...]int{
		-32, 100, 178, 132, 4, 64, 51, -41, 41, 31, 548, 1, -48, 102, 891, 3154, 45, 78,
	}
	jj.nums = test[:]
	Sort(jj)

	fmt.Println(jj.nums)
}
